/*
 * Copyright (C) 2011 Nicola Bonzanni
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package nl.vu.few.ibivu.jlemon.algorithms;

import java.util.ArrayList;
import java.util.Collections;
import java.util.ListIterator;
import java.util.Map;

import nl.vu.few.ibivu.jlemon.ArcIterator;
import nl.vu.few.ibivu.jlemon.NodeIterator;
import nl.vu.few.ibivu.jlemon.NodeMap;
import nl.vu.few.ibivu.jlemon.NullMap;
import nl.vu.few.ibivu.jlemon.ReverseDigraph;
import nl.vu.few.ibivu.jlemon.concepts.Arc;
import nl.vu.few.ibivu.jlemon.concepts.Graph;
import nl.vu.few.ibivu.jlemon.concepts.Node;

public class Connectivity {
	private static class FillMapVisitor<N extends Node & Comparable<N>, A extends Arc & Comparable<A>, V>
			extends AbstractGraphVisitor<N, A> {
		Map<N, V> map;
		V value;

		public FillMapVisitor(Map<N, V> map, V value) {
			this.map = map;
			this.value = value;
		}

		@Override
		public void reach(N node) {
			map.put(node, value);
		}

		public void setValue(V value) {
			this.value = value;
		}

	}

	private static class LeaveOrderVisitor<N extends Node & Comparable<N>, A extends Arc & Comparable<A>>
			extends AbstractGraphVisitor<N, A> {
		private ListIterator<N> it;

		public LeaveOrderVisitor(ListIterator<N> it) {
			this.it = it;
		}

		@Override
		public void leave(N node) {
			it.add(node);
		}
	}

	// /
	// / \brief Find the strongly connected components of a directed graph
	// /
	// / This function finds the strongly connected components of the given
	// / directed graph. In addition, the numbering of the components will
	// / satisfy that there is no arc going from a higher numbered component
	// / to a lower one (i.e. it provides a topological order of the
	// components).
	// /
	// / The strongly connected components are the classes of an
	// / equivalence relation on the nodes of a digraph. Two nodes are in
	// / the same class if they are connected with directed paths in both
	// / direction.
	// /
	// / \image html strongly_connected_components.png
	// / \image latex strongly_connected_components.eps
	// "Strongly connected components" width=\textwidth
	// /
	// / \param digraph The digraph.
	// / \retval compMap A writable node map. The values will be set from 0 to
	// / the number of the strongly connected components minus one. Each value
	// / of the map will be set exactly once, and the values of a certain
	// / component will be set continuously.
	// / \return The number of strongly connected components.
	// / \note By definition, the empty digraph has zero
	// / strongly connected components.
	// /
	// / \see stronglyConnected(), countStronglyConnectedComponents()
	public static <N extends Node & Comparable<N>, A extends Arc & Comparable<A>> int stronglyConnectedComponents(
			Graph<N, A> graph, NodeMap<N, Integer> compMap) {

		ArrayList<N> nodes = new ArrayList<N>(graph.nodeNum());
		LeaveOrderVisitor<N, A> visitor = new LeaveOrderVisitor<N, A>(nodes.listIterator());

		DfsVisit<N, A> dfs = new DfsVisit<N, A>(graph, visitor);
		dfs.init();
		for (NodeIterator<N> iterator = new NodeIterator<N>(graph); iterator.hasNext();) {
			N node = iterator.next();
			if (!dfs.reached(node)) {
				dfs.addSource(node);
				dfs.start();
			}
		}
		ReverseDigraph<N, A> rGraph = new ReverseDigraph<N, A>(graph);

		int compNum = 0;

		FillMapVisitor<N, A, Integer> rVisitor = new FillMapVisitor<N, A, Integer>(compMap, compNum);

		DfsVisit<N, A> rDfs = new DfsVisit<N, A>(rGraph, rVisitor);
		rDfs.init();
		for (ListIterator<N> rIterator = nodes.listIterator(nodes.size()); rIterator.hasPrevious();) {
			N node = rIterator.previous();
			if (!rDfs.reached(node)) {
				rDfs.addSource(node);
				rDfs.start();
				rVisitor.setValue(++compNum);
			}
		}
		return compNum;
	}

	// / \ingroup graph_properties
	// /
	// / \brief Find the connected components of an undirected graph
	// /
	// / This function finds the connected components of the given undirected
	// / graph.
	// /
	// / The connected components are the classes of an equivalence relation
	// / on the nodes of an undirected graph. Two nodes are in the same class
	// / if they are connected with a path.
	// /
	// / \image html connected_components.png
	// / \image latex connected_components.eps "Connected components"
	// width=\textwidth
	// /
	// / \param graph The undirected graph.
	// / \retval compMap A writable node map. The values will be set from 0 to
	// / the number of the connected components minus one. Each value of the map
	// / will be set exactly once, and the values of a certain component will be
	// / set continuously.
	// / \return The number of connected components.
	// / \note By definition, the empty graph consists
	// / of zero connected components.
	// /
	// / \see connected(), countConnectedComponents()
	public static <N extends Node & Comparable<N>, A extends Arc & Comparable<A>> int connectedComponents(
			Graph<N, A> graph, NodeMap<N, Integer> compMap) {

		int compNum = 0;
		Bfs<N, A> bfs = new Bfs<N, A>(graph, new NullMap<N, A>(), new NullMap<N, Integer>());

		bfs.init();
		for (NodeIterator<N> n = new NodeIterator<N>(graph); n.hasNext();) {
			n.next();
			if (!bfs.reached(n.peek())) {
				bfs.addSource(n.peek());
				while (!bfs.emptyQueue()) {
					compMap.put(bfs.nextNode(), compNum);
					bfs.processNextNode();
				}
				++compNum;
			}
		}
		return compNum;
	}
	
	public static <N extends Node & Comparable<N>, A extends Arc & Comparable<A>> int terminalComponents(
			Graph<N, A> graph, NodeMap<N, Integer> compMap, Map<Integer,Boolean> termMap) {

		int compMax = Collections.max(compMap.values());
		int compNum = 0;
		
		termMap.clear();
		for (int i = 0; i <= compMax; i++) {
			termMap.put(i, true);
		}
		
		for (ArcIterator<A> a = new ArcIterator<A>(graph); a.hasNext();) {
			a.next();
			int sourceComp = compMap.get(graph.source(a.peek()));
			int targetComp = compMap.get(graph.target(a.peek()));
			if (sourceComp != targetComp) {
				if (termMap.put(sourceComp, false)) {
					// if sourceComp was believed to be terminal
					compNum++;
				}
			}
		}
		
		return compMax - compNum + 1;
	}
}
